#ifndef DISJOINT_SET_H
#define DISJOINT_SET_H

#include "../types.h"

/*
1 给定一个等价关系"~",一个自然的问题是对任意的a和b,确定是否a~b。问题在于，这种关系的定义通常不明显而是相当隐秘的。
2 一个元素a∈S的等价类是S的一个子集，它包含所有与a有关系的元素。注意，等价类形成对S的一个划分：S的每一个成员恰好出现在一个等价类中。
    为确定是否a~b,我们只需验证a和b是否都在同一个等价类中。
3 输入数据最初是N个集合的类，每个集合含有一个元素。初始的描述是所有的关系均为false(自反的关系除外)。每个集合都有一个不同的元素，从而Si∩Sj=∅；这使得这些集合不相交。
4 该算法是动态的，因为在算法执行的过程中，集合可以通过Union运算发生改变。这个算法还必然是联机操作：当Find执行时，他必须给出答案算法才能继续进行。
    另一种可能是脱机算法：该算法需要观察全部的Union和Find序列。
5 注意，我们不进行任何比较元素相关的值的操作，而是只需要知道它们的位置。由于这个原因，我们假设所有的元素均已从1到N顺序编号并且编号方法容易由某个散列方案确定。
    于是，开始时我们有Si={i},i=1到N。
6 Find(a)=Find(b)当且仅当a和b在同一个集合中。
7 这些运算在许多图论问题中是重要的，在一些处理等价(或类型)声明的编译程序中也很重要。
8 解决动态等价问题的方案有两种。一种方案保证指令Find能够以常数最坏情形运行时间执行，而另一种方案则保证指令Union能够以常数最坏情形运行时间执行。
9 为使Find运算快，可以在一个数组中保存每个元素的等价类的名字。
10 一种想法是将所有在同一个等价类中的元素放到一个链表中。

1 记住，我们的问题不要求Find操作返回任何特定的名字，而只是要求当且仅当两个元素属于相同的集合时，作用在这两个元素上的Find返回相同的名字。
    一种想法是可以使用树来表示每一个集合，因为树上的每一个元素都有相同的根。这样，该根就可以用来命名所在的集合。我们将用树表示每一个集合。
2 数组的每个成员P[i]表示元素i的父亲。如果i是根，那么P[i]=0。
3 我们采纳了在Union(X,Y)后新的根是X的约定。
4 对元素X的一次Find(X)操作通过返回包含X的树的根而完成。
5 平均运行时间依赖于模型。
*/

#define NumSets 8

typedef int DisjSet[NumSets+1];
typedef int SetType;
typedef int ElementType;

void Initilialize(DisjSet S);
void SetUnion(DisjSet S, SetType Root1, SetType Root2);
SetType Dj_Find(ElementType X, DisjSet S);

#endif
